package com.zsj.heap;

import lombok.Getter;

import java.util.Arrays;

/**
 * @Author zsj
 * @Version 1.0
 * @Date 2024/4/2 18:43
 * @Description 大顶堆
 */
public class MaxHeap {

    int[] array;

    @Getter
    int size;

    public MaxHeap(int capacity) {
        array = new int[capacity];
    }

    public MaxHeap(int[] array) {
        this.array = array;
        this.size = array.length;
        heapify();
    }

    //建堆方法
    private void heapify() {
        //弗洛伊德建堆算法
        //找到最后一个非叶子节点  size /2 -1
        //size的位置就是我们数组中的最后一个元素 向上找父节点不用我多说
        //从后向前  对每一个节点进行下潜
        for (int i = (size >> 1) - 1; i >= 0; i--) {
            down(i);
        }
    }

    //根据索引删除元素
    public int poll(int index) {
        if (isEmpty()) throw new RuntimeException("array is empty");
        int deleted = array[index];
        swap(index, size - 1);
        size--;
        down(index);
        return deleted;
    }

    //获取顶部元素 移除
    public int poll() {
        if (isEmpty()) throw new RuntimeException("array is empty");
        //弹出顶部元素
        int ans = array[0];
        swap(0, size - 1);
        size--;
        down(0);
        return ans;
    }

    //获取顶部元素 不移除
    public int peek() {
        return array[0];
    }

    /**
     * 往堆尾部添加元素
     *
     * @param value 添加的元素
     * @return 添加结果
     */
    public boolean offer(int value) {
        if (isFull()) return false;
        array[size++] = value;
        up(size - 1);
        return true;
    }

    //上浮方法
    public void up(int offered) {
        //floor((i-1)/2) java中自动向下取整的 不需要我们手动
        int parent = (offered - 1) / 2;//计算出父节点的值
        if (offered != 0 && array[offered] > array[parent]) {
            //如果添加的值大于父节点 交换两个节点的值
            swap(offered, parent);
            up(parent);//继续上浮
        }
        //非递归版实现
//        while (offered != 0 && array[offered] > array[parent]) {
//            swap(offered, parent);
//            offered = (offered - 1) / 2;
//        }
    }

    /**
     * 替换堆顶元素
     *
     * @param replaced 替换值
     */
    public void replace(int replaced) {
        array[0] = replaced;
        down(0);
    }

    /**
     * 下潜方法
     *
     * @param parent 需要下潜元素的索引值
     */
    public void down(int parent) {
        int left = parent * 2 + 1;//找到左孩子
        int right = left + 1;//右孩子
        int max = parent;//较大值 默认为parent索引处的值
        if (left < size && array[left] > array[max]) {
            //如果左索引为有效索引且索引位置元素大于parent处元素
            //将较大值转换为left处的索引
            max = left;
        }
        if (right < size && array[right] > array[max]) {
            max = right;
        }
        if (max != parent) {
            //说明已经找到了比paren处大的值 对两个值进行交换
            swap(max, parent);
            down(max);
        }

    }


    //交换两个索引处位置的值
    private void swap(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == array.length;
    }

    public boolean hasNext() {
        return size != 0;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 1, 4};//123568
        //堆排序
        /*
        交换顶部和尾部--的位置的元素 交换一次需要将堆恢复大顶堆（除了尾部元素外）
        一直重复此操作 直到堆中只剩一个元素没有被交换过 堆排序就完成了
         */
        MaxHeap maxHeap = new MaxHeap(arr);

        System.out.println(Arrays.toString(maxHeap.array));

    }

}
